/**
 * n elements, value between 1,2,0, sort this array.
 */
class Solution{
public:
	// 时间复杂度 O(n)  空间复杂度 O(k) k为元素取值范围
	void sortColors(vector<int> &nums) {
		int count[3] = {0};    // 存放0, 1, 2三个元素的频率

		// 存储  0 1 2 元素个数
        for(int i = 0 ; i < nums.size() ; i ++){
            assert(nums[i] >= 0 && nums[i] <= 2);
            count[nums[i]] ++;
        }

		// 计数排序算法 优化
        int index = 0;
		// 将 0,1,2 按顺序排放在数组
        for(int i = 0 ; i < count[0] ; i ++)
            nums[index++] = 0;
        for(int i = 0 ; i < count[1] ; i ++)
            nums[index++] = 1;
        for(int i = 0 ; i < count[2] ; i ++)
            nums[index++] = 2;
	}

	/** zero index record o position.
	 * arr[0...zero]==0
     * arr[zero+1...i-1] 
     * arr[two...n-1] == 2
	 * [O(n), O(1)] 只遍历一遍
	 */
	void sortColors2(vector<int> &nums){
		int zero = -1;
		int two = nums.size();
		for(int i = 0;i < two;){
			if(nums[i] == 1)
				i++;
			else if(nums[i] == 2)
				swap(nums[i], nums[--two]);
			else{
				assert(nums[i] == 0);
				swap(nums[++zero], nums[i++]);
			}
		}
	}
};
